/**
 * 
 * 孪生和
 * 第i个节点的孪生节点为n-i-1，就是对称过去的那个节点
 * 
 * 问题：求长度为n的节点没有头节点的单链表的最大孪生和
 * 这里求和不是关键，因为这里是链表，所以不可能直接用a[i]+a[n-i-1]这样求
 * 所以关键是如何将链表整理的比较好球
 * 
 * 这里的链表长度n是偶数
 * 解法：快慢指针找最后尾节点，当fast到达尾节点时，slow就是n/2个节点
 * 然后将后半部分逆置
 * 设置p1 p2分别指向前半部分的头和后半部分的头
 * 求和并维护最大值即可
 * 
 * 
 * O(n)
 * O(1)
 */

#include"LinkedList.h"
int pairSum(LinkedList *l){
    LinkedList *fast=l->next,*slow=l;
    //fast找到第n个节点，slow找到n/2个节点
    while (fast!=nullptr&&fast->next!=nullptr)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    LinkedList *newHead=nullptr,*p=slow->next,*tmp;
    while (p!=nullptr)
    {
        tmp=p->next;//保存p的next，后面将p节点的next指向他的前一个之后就无法找到当前的next了
        p->next=newHead;//反转p.next指针
        newHead=p;//新的head往右移动
        p=tmp;//p移动到之前的next
    }
    //使用两个头开始计算和
    int max=0;p=l;
    LinkedList *q=newHead;
    while (p!=nullptr)
    {
        if((p->val+q->val)>max){
            max=(p->val+q->val);
        }
        p=p->next;
        q=q->next;
    }
    return max;
    
    
    
}

